package com.zhangc.ag;

/**
 * 功能描述:<br>
 * 4，上台阶问题，一个阶梯有N个台阶，每次只能上一步或者3步，求一共有多少种不同的方式上台阶
 * 例:N=50
 * 输出:122106097
 *
 * @author
 * @see [相关类/方法]（可选）
 * @since [产品/模块版本] （可选）
 */
public class alg4 {
    public static void main(String[] args) {

        int n = 50;
        System.out.println(climbStairs2(n));
    }

    public static double climbStairs2(int n) {
        //特判，防止n=1时dp[2]下标越界
        if (n == 1) {
            return 1;
        }
        //定义数组用来存储每次计算的结果
        double[] dp = new double[n + 1];
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 2;
        for (int i = 4; i <= n; i++) {
            //状态转移方程
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[n];
    }

    public static int climbStairs(int n) {
        double sqrt5 = Math.sqrt(5);
        double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
        return (int) Math.round(fibn / sqrt5);

        //        int p = 0, q = 0, r = 1;
        //        for (int i = 1; i <= n; ++i) {
        //            p = q;
        //            q = r;
        //            r = p + q;
        //        }
        //        return r;
    }

    public static int getStep(int n) {
        if (n <= 0)
            return 0;
        else if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 1;
        } else if (n == 3) {
            return 2;
        }

        return getStep(n - 1) + getStep(n - 2) + getStep(n - 3);
    }
}
